#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int n;
    char from, to, via;
    int phase;
} Frame;

typedef struct {
    Frame* items;
    int top;
    int size;
} Stack;

Stack create_stack(int size) {
    Stack s;
    s.items = (Frame*)malloc(size * sizeof(Frame));
    s.top = -1;
    s.size = size;
    return s;
}

void push(Stack* s, Frame f) {
    if (s->top >= s->size - 1) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->items[++s->top] = f;
}

Frame pop(Stack* s) {
    if (s->top < 0) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->items[s->top--];
}

void hanoi(int disks, char from, char to, char via) {
    Stack s = create_stack(2 * disks);
    push(&s, (Frame) { disks, from, to, via, 0 });

    while (s.top >= 0) {
        Frame f = pop(&s);

        if (f.n == 1) {
            printf("Move disk 1 from %c to %c\n", f.from, f.to);
        }
        else {
            if (f.phase == 0) {
                push(&s, (Frame) { f.n, f.from, f.to, f.via, 1 });
                push(&s, (Frame) { f.n - 1, f.from, f.via, f.to, 0 });
            }
            else if (f.phase == 1) {
                printf("Move disk %d from %c to %c\n", f.n, f.from, f.to);
                push(&s, (Frame) { f.n - 1, f.via, f.to, f.from, 0 });
            }
        }
    }

    free(s.items);
}

int main() {
    int n;
    printf("Number of disks: ");
    scanf("%d", &n);

    hanoi(n, 'A', 'C', 'B');
    return 0;
}
